<html>
<head><meta charset="utf-8"><title>AST(&quot;CST&quot;)/parsing evolution · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html">AST(&quot;CST&quot;)/parsing evolution</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="164615356"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164615356" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164615356">(May 01 2019 at 10:55)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> <span class="user-mention" data-user-id="116009">@nikomatsakis</span> I started writing <a href="https://hackmd.io/zrZhb94HS6KxW3sguwXNqA" target="_blank" title="https://hackmd.io/zrZhb94HS6KxW3sguwXNqA">https://hackmd.io/zrZhb94HS6KxW3sguwXNqA</a> btw, if you want to follow along as I do this :)</p>



<a name="164618727"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164618727" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164618727">(May 01 2019 at 12:09)</a>:</h4>
<p>wait what, where did the folder go?!</p>



<a name="164618886"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164618886" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164618886">(May 01 2019 at 12:12)</a>:</h4>
<p><span class="user-mention" data-user-id="120989">@nnethercote</span> <span class="user-mention" data-user-id="123856">@Vadim Petrochenkov</span> IMO <a href="https://github.com/rust-lang/rust/pull/58061" target="_blank" title="https://github.com/rust-lang/rust/pull/58061">https://github.com/rust-lang/rust/pull/58061</a> is a serious step backward, I don't know how to make any progress without reverting it...</p>



<a name="164619027"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164619027" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164619027">(May 01 2019 at 12:15)</a>:</h4>
<p>so there's our first action item: reverting a PR 3 months after it landed because I didn't realize it fully replaced the existing thing</p>



<a name="164619647"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164619647" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Vadim Petrochenkov <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164619647">(May 01 2019 at 12:26)</a>:</h4>
<p>What is the problem exactly?<br>
Everything doable in a folder should be doable in a mutable visitor as well?</p>



<a name="164619734"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164619734" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Vadim Petrochenkov <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164619734">(May 01 2019 at 12:28)</a>:</h4>
<p>Fold is representable as "clone + modify", and the result still can be allocated into an immutable arena if necessary, I think.</p>



<a name="164620976"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164620976" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164620976">(May 01 2019 at 12:53)</a>:</h4>
<p><span class="user-mention" data-user-id="123856">@Vadim Petrochenkov</span> see the hackmd link above, at the bottom (above the "generativity" bullet-point, I should find a way to hide that part)</p>



<a name="164621048"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621048" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621048">(May 01 2019 at 12:55)</a>:</h4>
<p>you want to be able to dynamically decide not to change anything, without a separate deep immutable visit</p>



<a name="164621143"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621143" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621143">(May 01 2019 at 12:57)</a>:</h4>
<p>so if you want to enforce mutation is detected, on top of that, you want to go as far away as possible from mutating nodes directly</p>



<a name="164621171"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621171" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621171">(May 01 2019 at 12:57)</a>:</h4>
<p>I consider unconditional deep cloning a non-starter</p>



<a name="164621237"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621237" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621237">(May 01 2019 at 12:58)</a>:</h4>
<p>while <code>T -&gt; T</code> and <code>&amp;mut T -&gt; ()</code> are somewhat equivalent, only the former lets you vary the input and output independently</p>



<a name="164621355"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621355" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621355">(May 01 2019 at 13:00)</a>:</h4>
<p>so that PR removed the freedom to change the interface, in the name of performance (which was measured on a broken implementation - today's rustc, wrt proc macros, that is - so I'm not sure it even counts!)</p>



<a name="164621794"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621794" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621794">(May 01 2019 at 13:08)</a>:</h4>
<p>I mean, sure, you can have all your signatures be <code>&amp;mut &amp;'arena T -&gt; ()</code>, but at that point, that's pretty silly, since <code>&amp;'arena T</code> would be copyable, so you lose nothing, performance-wise, if you switch to <code>&amp;'arena T -&gt; &amp;'arena T</code></p>



<a name="164621903"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164621903" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164621903">(May 01 2019 at 13:10)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> I think I've covered most of the design space I've been thinking about lately, I'm curious if I missed anything</p>



<a name="164622613"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164622613" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164622613">(May 01 2019 at 13:22)</a>:</h4>
<p>anyway, I'll go have lunch now and then work on other things, but I can come back to this if there any remarks</p>



<a name="164623327"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164623327" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> nikomatsakis <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164623327">(May 01 2019 at 13:33)</a>:</h4>
<p>(I broke this out into a separate topic, <span class="user-mention" data-user-id="119009">@eddyb</span> -- I'll check out the hackmd soon)</p>



<a name="164623500"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164623500" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164623500">(May 01 2019 at 13:36)</a>:</h4>
<p>note that there's not much of an evolution written out, just a bunch of alternatives to how we do things today, and the pressing issue of AST -&gt; TokenStream (which today is arguably broken)</p>



<a name="164625649"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164625649" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164625649">(May 01 2019 at 14:06)</a>:</h4>
<p><span class="user-mention" data-user-id="119009">@eddyb</span> awesome write up! Seems like a good coverage indeed, left a couple of comments inline, which boil to:</p>
<ul>
<li>I wish we could relax constraint A (global IDs), and makes AST a value type. Valueness seems benefitial, if we want to cache results of macro expansion (b/c, if expansion can observe identity, we can't really cache it)</li>
<li>for "origin tracking", we, in theory, can git rid of <em>ranges</em> altogether, and instead use parse tree nodes as origin</li>
</ul>
<p>Additionally  (and which is totally not my area of expertise), I'd love to see motivation why "tracking original tokens" is a better solution in a given circumstances , than "fixing pretty-printing". I guess in theory we could fix pretty-printing to be 100% reliable, right? Long-term, this seems like a better approach, because it works with identity-less AST.</p>



<a name="164627015"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627015" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627015">(May 01 2019 at 14:25)</a>:</h4>
<p>you can cache the results, not sure why identity is a problem. it should never leak into e.g. proc macros</p>



<a name="164627027"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627027" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627027">(May 01 2019 at 14:26)</a>:</h4>
<p>you can't have 100% reliable pretty-printing</p>



<a name="164627081"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627081" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627081">(May 01 2019 at 14:26)</a>:</h4>
<p>without... a parse tree. which literally keeps the original tokens around!</p>



<a name="164627154"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627154" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627154">(May 01 2019 at 14:27)</a>:</h4>
<p>I really don't see how you can 100% remove identity</p>



<a name="164627248"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627248" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627248">(May 01 2019 at 14:28)</a>:</h4>
<p>oh one thing I didn't write is "relative/contextual identity" (which would let you reuse the same sub-tree in two places, e.g. when using <code>$foo</code> more than once in <code>macro_rules!</code>)</p>



<a name="164627765"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627765" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627765">(May 01 2019 at 14:35)</a>:</h4>
<p>I have the following plan (not fully implemented) for id-less syntax trees:</p>
<ul>
<li>syntax tree is a value-type parse tree</li>
<li>when we do name-resolution/macro-expansion, we assign ID's to HIR nodes. So, when you expand <code>foo::bar::baz!()</code>, you rezolve <code>foo::bar</code> to already constructed <code>hir::Module</code> with an identity, not to a syntax-tree node.</li>
</ul>
<p>This bit is ready, and more or less works in rust-analyzer.</p>
<p>For macro-expansion:</p>
<ul>
<li>store hygiene information alongside the parse tree</li>
<li>when converting parse tree to tokens for macro expansion, assign local ids to tokens (local id == just count tokens in a particular macro invocation)</li>
<li>macro expansion then produces a new token tree, with tokens with same ids</li>
<li>these new tokens are parsed back into parse tree, and the hygiene side-table is restored, based on token identities. </li>
</ul>
<p>This bit is completely vaporware at the moment :-)</p>



<a name="164627785"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627785" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627785">(May 01 2019 at 14:35)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> oh, also, you haven't seen my (crazier) def ideas, which change some of the dynamics here :P (but I don't think enough to fully replace the AST)</p>



<a name="164627797"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627797" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627797">(May 01 2019 at 14:35)</a>:</h4>
<p>this write-up took priority, but I should do the "def" one too soon</p>



<a name="164627918"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627918" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627918">(May 01 2019 at 14:36)</a>:</h4>
<p>That is, the single bit where we seem to really require IDs is macro expansion: we need to figure out which tokens in the expansion originated from which source tokens. </p>
<p>But this IDs are on the token trees, not on the AST.</p>



<a name="164627953"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627953" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627953">(May 01 2019 at 14:37)</a>:</h4>
<p>that's just implicit in rustc</p>



<a name="164627960"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627960" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627960">(May 01 2019 at 14:37)</a>:</h4>
<p>do you do name resolution on HIR?</p>



<a name="164627974"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164627974" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164627974">(May 01 2019 at 14:37)</a>:</h4>
<p>(for things other than macro invocations)</p>



<a name="164628043"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628043" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628043">(May 01 2019 at 14:38)</a>:</h4>
<p>if so, your "HIR" is our "AST" (or in the future, "Def"+"AST") :P</p>



<a name="164628059"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628059" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628059">(May 01 2019 at 14:38)</a>:</h4>
<p>tfw names stop being that useful</p>



<a name="164628065"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628065" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628065">(May 01 2019 at 14:38)</a>:</h4>
<p>:D</p>



<a name="164628174"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628174" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628174">(May 01 2019 at 14:40)</a>:</h4>
<p>if you add that "Def" layer around AST/HIR then, yes, you can do nicer things. in particular, you can assign IDs very early during parsing that you can keep using all the way to <del>the bank</del> codegen, and even across crates</p>



<a name="164628179"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628179" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628179">(May 01 2019 at 14:40)</a>:</h4>
<p>I run name resolution during translation from syntax trees to HIR.</p>
<p>The core thing is that macro expansion operates on stuff without identity</p>



<a name="164628203"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628203" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628203">(May 01 2019 at 14:40)</a>:</h4>
<p>and you can make the actually-trees of AST/HIR (Ty/Expr/Pat) far more value-like</p>



<a name="164628218"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628218" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628218">(May 01 2019 at 14:40)</a>:</h4>
<p>yeah, the name resolution algorithm we have doesn't really admit that</p>



<a name="164628240"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628240" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628240">(May 01 2019 at 14:41)</a>:</h4>
<p>because of all the stateful tracking</p>



<a name="164628267"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628267" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628267">(May 01 2019 at 14:42)</a>:</h4>
<p>rewriting that, backwards-compatibly (or even making a second implementation) will likely take a while, in a language like Rust</p>



<a name="164628315"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628315" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628315">(May 01 2019 at 14:42)</a>:</h4>
<p>and will need some amount of identity anyway</p>



<a name="164628338"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628338" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628338">(May 01 2019 at 14:42)</a>:</h4>
<p>that is undeniably true :-) Working with existing architecture is the only way to fix immediate problems</p>



<a name="164628357"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628357" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628357">(May 01 2019 at 14:43)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> again, this is offtopic, but, this is the diagram for the write-up I haven't done yet: today: <a href="https://bit.ly/2GBLppR" target="_blank" title="https://bit.ly/2GBLppR">https://bit.ly/2GBLppR</a> -&gt; future: <a href="https://bit.ly/2L4HYxp" target="_blank" title="https://bit.ly/2L4HYxp">https://bit.ly/2L4HYxp</a></p>



<a name="164628370"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628370" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628370">(May 01 2019 at 14:43)</a>:</h4>
<p>I hope it helps even a bit :P</p>



<a name="164628506"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628506" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628506">(May 01 2019 at 14:44)</a>:</h4>
<p>I read it as "Thing with <code>ID</code> is <code>Def</code>, and AST is a value-type attribute of DEF", and I like it :)</p>



<a name="164628522"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628522" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628522">(May 01 2019 at 14:45)</a>:</h4>
<blockquote>
<p>and will need some amount of identity anyway</p>
</blockquote>
<p>Where exactly do we need identity?</p>



<a name="164628876"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628876" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628876">(May 01 2019 at 14:49)</a>:</h4>
<p>referring to an invocation in a way that reflects its scope</p>



<a name="164628946"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164628946" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164628946">(May 01 2019 at 14:50)</a>:</h4>
<p>unless you want to use some sort of inverted tree to represent scopes (my head hurts just thinking of that)</p>



<a name="164629136"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629136" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629136">(May 01 2019 at 14:53)</a>:</h4>
<p>also, you can't map from an identity-less AST back to source in any meaningful way (assuming you remove <code>Span</code> too) without either a tree that has the same shape as with an identity-based AST, or some relative scheme - I guess I could see an identity-less Parse Tree working, but since that would include all the tokens, I don't know... we'll have to explore this further in the future</p>



<a name="164629192"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629192" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629192">(May 01 2019 at 14:54)</a>:</h4>
<blockquote>
<p>"AST is a value-type attribute of DEF",</p>
</blockquote>
<p>Kinda! <code>{ast,hir}::{Ty,Expr,Pat}</code> would be hanging off the <code>Def</code>s (which would correspond to things that have <code>DefId</code>s today)</p>



<a name="164629194"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629194" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629194">(May 01 2019 at 14:54)</a>:</h4>
<p>oops, accidentally sent partial message</p>



<a name="164629202"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629202" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629202">(May 01 2019 at 14:54)</a>:</h4>
<p>in ra, we refer to macro invocations by a pair of (FileId, InFileSpan), where <code>FileId</code> contains "identity" bits (So it's more like a current module, rathet than a file), and <code>InFileSpan</code> is a pointer into <code>AST</code>, which is a value type</p>



<a name="164629291"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629291" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629291">(May 01 2019 at 14:55)</a>:</h4>
<p>okay so that's just the relative scheme I was talking about</p>



<a name="164629396"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629396" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629396">(May 01 2019 at 14:56)</a>:</h4>
<p>where <code>FileId</code> is the container (which I want to focus around tokens, because that's what proc macros output)</p>



<a name="164629400"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629400" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629400">(May 01 2019 at 14:56)</a>:</h4>
<p>yeah, with a twist that the node itself doesn't know it's id</p>



<a name="164629403"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629403" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629403">(May 01 2019 at 14:56)</a>:</h4>
<p>oh I also meant to say I replied to your comments</p>



<a name="164629430"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629430" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629430">(May 01 2019 at 14:57)</a>:</h4>
<p>if you're using pointers for identity, that's isomorphic to having an ID inside :P</p>



<a name="164629455"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629455" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629455">(May 01 2019 at 14:57)</a>:</h4>
<p>or to replacing the pointers (to children nodes) with IDs allocated in an array</p>



<a name="164629462"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629462" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629462">(May 01 2019 at 14:57)</a>:</h4>
<blockquote>
<p>if you're using pointers for identity, that's isomorphic to having an ID inside :P</p>
</blockquote>
<p>Nope: macro call doesn't know <code>FileId</code></p>



<a name="164629514"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629514" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629514">(May 01 2019 at 14:58)</a>:</h4>
<p><code>FileId</code> is the contextual part, I'm referring to <code>InFileSpan</code></p>



<a name="164629611"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629611" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629611">(May 01 2019 at 14:59)</a>:</h4>
<p>I woldn't call <code>InFileSpan</code> and id: it's positional, and not identity based. Like <code>0..5</code> is not and ID of <code>hello</code> in <code>"hello, world"</code>, because it works for any copy of <code>"hello world"</code></p>



<a name="164629655"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629655" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629655">(May 01 2019 at 15:00)</a>:</h4>
<p>so, this might be just a question of terminology :)</p>



<a name="164629672"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629672" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629672">(May 01 2019 at 15:00)</a>:</h4>
<p>so you're not really missing global identity (since <code>(FileId, InFileSpan)</code> is just that), it's just relative, which has benefits (if we can get it to work)</p>



<a name="164629757"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629757" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629757">(May 01 2019 at 15:01)</a>:</h4>
<p>Yeah, I have global identity, but it is strictly outside the tree itself. I think it useful when implementing refactorings or other things which need to generate syntax on the fly. </p>
<p>If you generate syntax trees out of thin air, its good if you don't need to care how to assign identity to them</p>



<a name="164629759"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629759" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629759">(May 01 2019 at 15:01)</a>:</h4>
<p>I've talked before about the relative ID thing as being the ultimate evolution of "token ranges", I just don't know how to use it to optimize certain things correctly</p>



<a name="164629778"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629778" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629778">(May 01 2019 at 15:01)</a>:</h4>
<p>okay, yeah, something I should've pointed out is that the nodes don't need to know their identity</p>



<a name="164629824"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629824" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629824">(May 01 2019 at 15:02)</a>:</h4>
<p>you just need to be able to obtain it while visiting them, starting from some root</p>



<a name="164629859"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164629859" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164629859">(May 01 2019 at 15:02)</a>:</h4>
<p>let me reread that section and perhaps amend it, to make this clearer</p>



<a name="164630039"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630039" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630039">(May 01 2019 at 15:04)</a>:</h4>
<p>(sorry for getting a bit confused and assuming that you truly had no sort of global identity and instead were doing some things value-based)</p>



<a name="164630086"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630086" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630086">(May 01 2019 at 15:05)</a>:</h4>
<blockquote>
<p>also, you can't map from an identity-less AST back to source in any meaningful way</p>
</blockquote>
<p>This actually works quite successfully in rust-analyzer. We use a "source-map" pattern for this: when we lower raw syntax to HIR, we produce a pair of <code>(HIR, SourceMap)</code>, where HIR is an ID-based arena allocated graph, and <code>SourceMap</code> is an <code>FxHashMap&lt;HirId, SourceNode&gt;</code>. </p>
<p>The cool bit here is that HIr becomes completely independent of the source representation! So, if you edit the source such that HIR is the same, then only <code>SourceMap</code> component changes. Because almost no code looks at the source-map, that makes stuff super-incremental</p>



<a name="164630172"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630172" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630172">(May 01 2019 at 15:06)</a>:</h4>
<p>Yeah, I could also have been more clear that I argue not against global ids per-se, but against syntax trees, which <strong>know</strong> their identity.</p>



<a name="164630650"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630650" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630650">(May 01 2019 at 15:13)</a>:</h4>
<p>yeah when I said identity-less I meant "it's really gone, completely"</p>



<a name="164630816"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630816" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630816">(May 01 2019 at 15:15)</a>:</h4>
<p><span class="user-mention" data-user-id="133169">@matklad</span> added a pagaraph to <a href="https://hackmd.io/zrZhb94HS6KxW3sguwXNqA?view#A-Global-node-identity-unique-precise-lossless" target="_blank" title="https://hackmd.io/zrZhb94HS6KxW3sguwXNqA?view#A-Global-node-identity-unique-precise-lossless">https://hackmd.io/zrZhb94HS6KxW3sguwXNqA?view#A-Global-node-identity-unique-precise-lossless</a></p>



<a name="164630888"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630888" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630888">(May 01 2019 at 15:16)</a>:</h4>
<p>(I can't think of a way to integrate it into the above bullet-point, I wish there was an easier way to describe multi-dimensional design spaces :P)</p>



<a name="164630995"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164630995" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164630995">(May 01 2019 at 15:17)</a>:</h4>
<p>Can't you insert raw-html with <code>position: absolute</code> and appropriate z-index? /s :D</p>



<a name="164631053"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164631053" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164631053">(May 01 2019 at 15:18)</a>:</h4>
<p>you mean 3D CSS transforms :P?</p>



<a name="164631238"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164631238" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164631238">(May 01 2019 at 15:20)</a>:</h4>
<p>okay this has been a bit offtopic, but I guess it all overlaps enough that there's no reason to split the Zulip topic or w/e. also, I really wanted to go work on a few other things, so I'll get back to this maybe tomorrow or on Friday</p>



<a name="164797396"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797396" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797396">(May 03 2019 at 14:13)</a>:</h4>
<p><span class="user-mention" data-user-id="119009">@eddyb</span> moved out the weeds out of steering meeting :D</p>



<a name="164797460"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797460" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797460">(May 03 2019 at 14:14)</a>:</h4>
<p>idk if these are weeds, and, like, we have the other topic already?</p>



<a name="164797668"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797668" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797668">(May 03 2019 at 14:16)</a>:</h4>
<p>So, agree 100% that mem-management is imiportant, and, more generally, the lifetime of syntax trees (when in gets destroied). In rust-analyzer, syntax trees weight a ton, due to all of comments and whitespace :-( My plan is to make sure that only a small fraction of syntax trees is kept in memory, and that the are loaded and unloaded on-demand</p>



<a name="164797740"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797740" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797740">(May 03 2019 at 14:17)</a>:</h4>
<p>that is, besides optimizing just the memory footprint of the datastructure, we might be able to save mem by a sort-of "overlay" system, where you look only at a section of a tree at a time, jsut to convert it to HIR</p>



<a name="164797751"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797751" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797751">(May 03 2019 at 14:17)</a>:</h4>
<p>well, specifically I am interested in the AST which destroys parse tree minutiae like that, and the transitionary period of "we still have some sort of AST mutation" as opposed to all expansion being done in a very "functional" manner</p>



<a name="164797846"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164797846" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> eddyb <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164797846">(May 03 2019 at 14:18)</a>:</h4>
<p>I definitely agree with you, if we were to have a true parse tree (based on GLL or anything else)</p>



<a name="164840350"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/AST%28%22CST%22%29/parsing%20evolution/near/164840350" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/AST(.22CST.22).2Fparsing.20evolution.html#164840350">(May 04 2019 at 00:05)</a>:</h4>
<p>Semi-related: I got curious about how Swift parser is set-up to produce an AST and a CST simultaneously. Swift doesn't build AST from CST, rather, both are produced at the same time for historical reasons which will probably apply to Rust as well, when we have a CST.</p>
<p>And turns out there's no magic: in each parsing function, there are two pieces of code: for AST and for CST. Here's how a simple expression is parsed (&lt;expr-is&gt;, I assume some kind of instanceof check):</p>
<ul>
<li>explicit AST construction: <a href="https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L86" target="_blank" title="https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L86">https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L86</a></li>
<li>explicit (but RAII-based) CST construction: <a href="https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L306" target="_blank" title="https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L306">https://github.com/apple/swift/blob/d0ae1d979856e874b4d4fba3930c87a14fd3fa3f/lib/Parse/ParseExpr.cpp#L306</a></li>
</ul>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>